package ljl.alg.wangzheng_camp.round1.bfsdfs;

import java.util.*;

public class _16_19_pond_size {
    
    static class dfs {
        public int[] pondSizes(int[][] land) {
            class T {
                static final int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {1, 1}, {1, -1}, {-1, 0}, {-1, 1}, {-1, -1}};
                
                static int dfs(int[][] land, int i, int j) {
                    if (i < 0 || i >= land.length || j >= land[0].length || j < 0 || land[i][j] != 0)
                        return 0;
                    land[i][j] = 1;
                    int res = 1;
                    for (int[] dir : dirs) {
                        res += dfs(land, i + dir[0], j + dir[1]);
                    }
                    return res;
                }
            }
            int m = land.length, n = land[0].length;
            
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (land[i][j] == 0)
                        res.add(T.dfs(land, i, j));
                }
            }
            Collections.sort(res);
            return res.stream().mapToInt(Integer::valueOf).toArray();
        }
        
        
    }
    
    static class bfs {
        /**
         * 聪明版
         */
        public int[] pondSizes(int[][] land) {
            int m = land.length, n = land[0].length;
            List<Integer> res = new ArrayList<>();
            int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 1}, {1, -1}, {1, 0}, {-1, 1}, {-1, -1}, {-1, 0}};
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (land[i][j] == 0) {
                        land[i][j] = 1;
                        LinkedList<int[]> q = new LinkedList<>();
                        q.offer(new int[]{i, j});
                        int size = 0;
                        while (!q.isEmpty()) {
                            size++;
                            int[] pos = q.poll();
                            for (int[] dir : dirs) {
                                int x = pos[0] + dir[0], y = pos[1] + dir[1];
                                System.out.println(Arrays.toString(pos) + " -> " + x + ", " + y);
                                if (x < 0 || y < 0 || x >= m || y >= n || land[x][y] != 0)
                                    continue;
                                q.offer(new int[]{x, y});
                                land[x][y] = 1;
                            }
                        }
                        res.add(size);
                    }
                }
            }
            Collections.sort(res);
            return res.stream().mapToInt(Integer::valueOf).toArray();
        }
        
        /**
         * 没有功劳也有苦劳
         */
        public int[] pondSizes2(int[][] land) {
            int m = land.length, n = land[0].length;
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (land[i][j] == 0) {
                        land[i][j] = 1;
                        int size = 0;
                        LinkedList<int[]> q = new LinkedList<>();
                        q.offer(new int[]{i, j});
                        while (!q.isEmpty()) {
                            size++;
                            int[] pos = q.poll();
                            int x = pos[0], y = pos[1];
                            if (x + 1 < m) {
                                if (land[x + 1][y] == 0) {
                                    land[x + 1][y] = 1;
                                    q.offer(new int[]{x + 1, y});
                                }
                                if (y - 1 > -1 && land[x + 1][y - 1] == 0) {
                                    land[x + 1][y - 1] = 1;
                                    q.offer(new int[]{x + 1, y - 1});
                                }
                                if (y + 1 < n && land[x + 1][y + 1] == 0) {
                                    land[x + 1][y + 1] = 1;
                                    q.offer(new int[]{x + 1, y + 1});
                                }
                            }
                            if (x - 1 > -1) {
                                if (land[x - 1][y] == 0) {
                                    land[x - 1][y] = 1;
                                    q.offer(new int[]{x - 1, y});
                                }
                                if (y - 1 > -1 && land[x - 1][y - 1] == 0) {
                                    land[x - 1][y - 1] = 1;
                                    q.offer(new int[]{x - 1, y - 1});
                                }
                                if (y + 1 < n && land[x - 1][y + 1] == 0) {
                                    land[x - 1][y + 1] = 1;
                                    q.offer(new int[]{x - 1, y + 1});
                                }
                            }
                            if (y + 1 < n && land[x][y + 1] == 0) {
                                land[x][y + 1] = 1;
                                q.offer(new int[]{x, y + 1});
                            }
                            if (y - 1 > -1 && land[x][y - 1] == 0) {
                                land[x][y - 1] = 1;
                                q.offer(new int[]{x, y - 1});
                            }
                            
                        }
                        res.add(size);
                    }
                }
            }
            Collections.sort(res);
            return res.stream().mapToInt(Integer::valueOf).toArray();
        }
    }
    
    /*
    * func pondSizes(land [][]int) []int {
	if len(land) == 0 {
		return nil
	}
	s := newSet(land)

	for i := range land {
		for j := range land[i] {
			s.unionAround(j, i)
		}
	}
	mp := make(map[int]int)
	for i := range land {
		for j := range land[i] {
			// 如果得到的 int值， 对应于二维切片的值是0，那么就统计这个值
			a := s.find(j, i)
			x, y := s.dischange(a)
			if land[y][x] == 0 {
				if v, ok := mp[a]; ok {
					mp[a] = v+1
				} else {
					mp[a] = 1
				}
			}
		}
	}
	result := make([]int, 0, len(mp)) 1 1
	// mp 中有我们搜集的信息 v是大小
	for _, v := range mp {
		result = append(result, v)
	}

	sort.Ints(result)
	return result

}

func (s *set) unionAround(x, y int) {

	if x-1 > 0 {
		s.union(x, y, x-1, y)
	}
	if y-1 > 0 {
		s.union(x, y, x, y-1)
	}
	if x-1 > 0 && y-1 > 0 {
		s.union(x, y, x-1, y-1)
	}

	if x+1 < s.xl {
		s.union(x, y, x+1, y)
	}
	if y+1 < s.yl {
		s.union(x, y, x, y+1)
	}
	if x+1 < s.xl && y+1 < s.yl {
		s.union(x,y,x+1,y+1)
	}

	if x-1 > 0 && y+1 < s.yl {
		s.union(x, y, x-1, y+1)
	}
	if x+1 < s.xl && y-1 > 0 {
		s.union(x, y, x+1, y-1)
	}

}


type set struct {
	land [][]int
	s []int             // x*len(land[0]) + y
	xl int               // 记录 land[0].len
	yl int
}

func newSet(land [][]int) *set {
	xl, yl := len(land[0]), len(land)
	n := xl * yl
	s := make([]int, n)
	for i := range s {
		s[i] = i
	}
	return &set{land, s, xl, yl}
}

func (s *set)change(x, y int) int {
	return y * s.xl + x
}

func (s *set)dischange(a int) (x, y int) {
	x = a % s.xl
	y = a / s.xl
	return
}

func (s *set)find(x, y int) int {
	a := s.change(x, y)
	if s.s[a] == a {
		return a
	}
	return s.find(s.dischange(s.s[a]))
}

// 如果在一个集合不操作， 如果land(x,y)不等于0，不操作
func (s *set)union(x1, y1, x2, y2 int) {
	if s.land[y1][x1] != 0 || s.land[y2][x2] != 0 {
		return
	}
	if s.find(x1, y1) == s.find(x2, y2) {
		return
	}
	s.s[s.find(x1, y1)] = s.s[s.find(x2, y2)]
}
    * */
    
    /*
     * 这个题肯定可以并查集，试试吧，你都 31 岁了
     * */
    static class Solution {
        
        static class UnionFind {
            int[] rank, parents;
            
            UnionFind(int[][] land) {
                int m = land.length, n = land[0].length;
                rank = new int[m * n];
                parents = rank.clone();
                Arrays.fill(parents, -1);
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (land[i][j] == 0) {
                            parents[i * n + j] = i * n + j;
                        }
                    }
                }
            }
            
            void union(int x, int y) {
                int rx = find(x), ry = find(y);
                if (rank[rx] < rank[ry]) {
                    parents[rx] = ry;
                } else if (rx > ry) {
                    parents[ry] = rx;
                } else {
                    rank[rx]++;
                    parents[ry] = rx;
                }
            }
            
            int find(int i) {
                if (i != parents[i]) {
                    parents[i] = find(parents[i]);
                }
                return parents[i];
            }
            
            static int toInt(int x, int y, int n) {
                return x * n + y;
            }
        }
        
        public int[] pondSizes(int[][] land) {
            int m = land.length, n = land[0].length;
            int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 1}, {1, -1}, {1, 0}, {-1, 1}, {-1, -1}, {-1, 0}};
            UnionFind uf = new UnionFind(land);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (land[i][j] == 0) {
                        for (int[] dir : dirs) {
                            int x1 = i + dir[0], y1 = j + dir[1];
                            if (x1 < 0 || y1 < 0 || x1 >= m || y1 >= n || land[x1][y1] != 0)
                                continue;
                            uf.union(UnionFind.toInt(x1, y1, n), UnionFind.toInt(i, j, n));
                        }
                    }
                }
            }
            Map<Integer, Integer> counts = new HashMap<>();
            for (int parent : uf.parents) {
                if (parent < 0)
                    continue;
                int root = uf.find(parent);
                counts.put(root, counts.getOrDefault(root, 0) + 1);
            }
            List<Integer> res = new ArrayList<>(counts.values());
            Collections.sort(res);
            return res.stream().mapToInt(Integer::valueOf).toArray();
        }
        
    }
    
}
